package algorithm.leetcode.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 和为k的子数组
 */
public class SubArraySumToK {
    /**
     * 前缀和
     * sum[j..i] = pre[i] - pre[j-1]
     * k = pre[i] - pre[j-1]
     * pre[j-1] = pre[i] - k
     * Map<前缀和，前缀和出现的次数></>
     * 初始化 0 1
     * @param nums
     * @param k
     * @return
     */

    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        int sum = 0;
        int count = 0;
        for(int i=0; i<nums.length; i++) {
            //前缀和
            sum = sum + nums[i];
            //pre[j-1]
            int key = sum -k;
            //计算pre[j-1]是否出现过
            if(map.containsKey(key)) {
                int value = map.get(key);
                count = count + value;
            }
            //前缀和放入map中
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}
